﻿#pragma once

#include <iostream>
#include <vector>
#include <time.h>
#include <assert.h>
#include <unordered_map>
using std::cout;
using std::endl;
static const size_t MAX_SIZE = 256 * 1024;
static const size_t NFREELIST = 208;

class FreeList
{
public:
	void push(void* obj)
	{
		assert(obj);

		*(void**)obj = _freeList;
		_freeList = obj;
	}

	void* pop()
	{
		assert(_freeList);

		void* obj = _freeList;
		_freeList = *(void**)obj;
		return obj;
	}
private:
	void* _freeList;
};

// 计算对齐后的大小
class SizeClass
{
public:
	// 整体控制在最多10%左右的内碎⽚浪费
	// [1,128]					8byte对⻬		freelist[0,16)		16
	// [128+1,1024]				16byte对⻬		freelist[16,72)		56
	// [1024+1,8*1024]			128byte对⻬		freelist[72,128)	56
	// [8*1024+1,64*1024]		1024byte对⻬		freelist[128,184)	56
	// [64*1024+1,256*1024]		8*1024byte对⻬	freelist[184,208)	24

	static size_t _RoundUp(size_t size, size_t alignNum)
	{
		//return size % alignNum == 0 ? size : (size / alignNum + 1) * alignNum;
		return (size + alignNum - 1) & ~(alignNum - 1);
	}

	static size_t RoundUp(size_t size)
	{
		if (size <= 128)
		{
			return _RoundUp(size, 8);
		}
		else if (size <= 1024)
		{
			return _RoundUp(size, 16);
		}
		else if (size <= 8 * 1024)
		{
			return _RoundUp(size, 128);
		}
		else if (size <= 64 * 1024)
		{
			return _RoundUp(size, 1024);
		}
		else if (size <= 256 * 1024)
		{
			return _RoundUp(size, 8 * 1024);
		}
		else
		{
			assert(size <= MAX_SIZE);
			return -1;
		}
	}
	// 整体控制在最多10%左右的内碎⽚浪费
	// [1,128]					8byte对⻬		freelist[0,16)		16
	// [128+1,1024]				16byte对⻬		freelist[16,72)		56
	// [1024+1,8*1024]			128byte对⻬		freelist[72,128)	56
	// [8*1024+1,64*1024]		1024byte对⻬		freelist[128,184)	56
	// [64*1024+1,256*1024]		8*1024byte对⻬	freelist[184,208)	24

	// 非位运算写法
	/*size_t _index(size_t size, size_t alignShift)
	{
		size_t alignNum = pow(2, alignShift);
		return size % alignNum == 0 ? size / alignNum - 1 : size / alignNum;
	}*/

	static size_t _index(size_t size, size_t alignShift)
	{
		return ((size + (1 << alignShift) - 1) >> alignShift) - 1;
	}

	// 通过需要的字节数 ，算桶的下标
	static size_t Index(size_t size)
	{
		static size_t a[5] = { 16,56,56,56,24 };
		if (size <= 128)
		{
			return _index(size, 3);
		}
		else if (size <= 1024)
		{
			return _index(size - 128, 4) + a[0];
		}
		else if (size <= 8 * 1024)
		{
			return _index(size - 1024, 7) + a[0] + a[1];
		}
		else if (size <= 64 * 1024)
		{
			return _index(size - 8 * 1024, 10) + a[0] + a[1] + a[2];
		}
		else if (size <= 256 * 1024)
		{
			return _index(size - 64 * 1024, 18) + a[0] + a[1] + a[2] + a[3];
		}
		else
		{
			assert(size <= MAX_SIZE);
		}
	}
};